package com.lw.leetcode.linked.b;

import com.lw.leetcode.tree.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * 103. 二叉树的锯齿形层序遍历
 *
 * @author liw
 * @version 1.0
 * @date 2023/1/3 10:04
 */
public class ZigzagLevelOrder {

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> all = new ArrayList<>();
        if (root == null) {
            return all;
        }
        Stack<TreeNode> a = new Stack<>();
        Stack<TreeNode> b = new Stack<>();
        a.add(root);
        List<Integer> item;
        while (!a.isEmpty() || !b.isEmpty()) {
            item = new ArrayList<>();
            while (!a.isEmpty()) {
                TreeNode pop = a.pop();
                item.add(pop.val);
                if (pop.left != null) {
                    b.add(pop.left);
                }
                if (pop.right != null) {
                    b.add(pop.right);
                }
            }
            if (!item.isEmpty()) {
                all.add(item);
            }
            item = new ArrayList<>();
            while (!b.isEmpty()) {
                TreeNode pop = b.pop();
                item.add(pop.val);
                if (pop.right != null) {
                    a.add(pop.right);
                }
                if (pop.left != null) {
                    a.add(pop.left);
                }
            }
            if (!item.isEmpty()) {
                all.add(item);
            }
        }
        return all;
    }

}
